In the prior art communications of a data sequence using digital signals, error correcting is generally employed to correct errors caused by noise on the transmission channel by encoding the data sequence into error correcting codes when transmitting and decoding the data sequence when receiving by a scheme corresponding to the above mentioned encoding. Among the various encoding and decoding methods used in such a device, convolutional encoding and maximum likelihood decoding methods have been known as excellent methods.
A convolutional encoder having the coding rate: k.sub.0 /n.sub.1 =3/6=.kappa., and the constraint length :k=3 is exemplified in the following explanation. The coding rate means the rate of the number of bits of an input data sequence against the number of bits in a corresponding code sequence. In other words, the larger the coding rate means, the smaller the redundancy. The constraint length means the number of bits in an input data necessary to obtain an output code. In the case where the constraint length k is 3, an output code is obtained based upon an input data and two registered data.
FIG. 8 is a block diagram to show a prior art convolutional encoder wherein a data sequence D which is expressed by D=(D.sub.0, D.sub.1, D.sub.2, D.sub.3, D.sub.4 . . . is inputted at an input terminal 1. D.sub.0, D.sub.1, D.sub.2. . . denote respectively input bits at times t=0, 1, 2. . . A shift register 317 comprises three bits d.sub.0, d.sub.1, d.sub.2, and sequentially shifts and stores data sequence D. In other words, a data D.sub.t which is inputted at the time t at the input terminal 1, is stored at the bit d.sub.0 of the shift register 317 and is consecutively shifted to bits d.sub.l and d.sub.2 at the time t+1, and time t+2. The data stored at the bits d.sub.0 and d.sub.2 are calculated for exclusive OR by a modulo-2 adder and sent out to a transmission path from an output terminal 40 as an I channel code. The data stored at the bits d.sub.0, d.sub.1 and d.sub.2 are calculated for exclusive OR and sent out to a transmission path from an output terminal 41 as a Q channel code.
In short, code sequences I and Q EQU I=(I.sub.0, I.sub.1, I.sub.2 . . . ) EQU Q=(Q.sub.0, Q.sub.1, Q.sub.2 . . . )
are outputted from the output terminals 40 and 41 after the time t=2. Herein, EQU I.sub.t =D.sub.t +D.sub.t+2 EQU Q.sub.t =D.sub.t +D.sub.t+1 +D.sub.t+2 EQU t=0, 1, 2 . . .
[+] denotes an addition by a modulo-2 adder. The symbol [+] hereinafter denotes an addition by a modulo-2 adder.
FIG. 9 is a trellis diagram of the convolutional encoder as above described.
The state (d.sub.0, d.sub.1) indicates the content of the bits d.sub.0, d.sub.1 of the shift register 317 immediately before the input of an original data D.sub.t. Solid lines denote a state transition when D.sub.t =0, and broken lines a state transition when D.sub.t =1. The figures written near the lines denote respective outputs (I.sub.t,Q.sub.t) The table below indicates outputs (I.sub.t, Q.sub.t) in correspondence to the states (d.sub.0, d.sub.1).
TABLE ______________________________________ d.sub.0 d.sub.1 I.sub.t Q.sub.t ______________________________________ D.sub.t = 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 0 D.sub.t = 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 ______________________________________
A case where the shift register is (d.sub.0, d.sub.1)=(1, 0) will be exemplified for a descriptive purpose. When an input D.sub.t is [0], the output will be I.sub.t =0,Q.sub.t =1 and the shift register 317 will have the state EQU (d.sub.0, d.sub.1)=(0, 1).
When the data D.sub.t is [1], the output will be I.sub.t =1,Q.sub.t =0 and the shift register 317 will assume the state (d.sub.0, d.sub.1)=(1, 1).
The output from a convolutional decoder is transmitted through a transmission path and decoded by a maximum likelihood decoder. As the maximum likelihood decoder, a Viterbi decoder using Viterbi algorithm is generally used as it can execute estimations of the original data at a high efficiency. The Viterbi decoder decodes input data by seeking a path (history of state transistion) having the highest correlation or in other words having the smallest summing distance in respect of the received encoded data and estimating the original data based thereon.
FIG. 10 is a block diagram to show a conventional Viterbi decoder. A Viterbi decoder for a 3 bit soft decision is exemplified here for illustration purposes.
Incoming codes of I and Q channels via a transmission channel are quantized in soft-decision in respective 3 bits or 8 values and inputted at input terminals 70, 71 of the Viterbi decoder. A branch metric calculator 73 calculates correlation of a branch metric between input signals and state transitions in correspondence to the trellis diagram shown in FIG. 9. A path metric calculator 75 adds the output from the branch metric calculator 73 and the old path metric and calculates a new path metric. A path memory 76 stores history of a path which corresponds to the path metric. A final decision circuit 77 decides the final decoded output and outputs it to an output terminal 9.
FIG. 11 is a block diagram to show another prior art convolution encoder. This convolutional encoder is an encoder equivalent to the above prior art encoder comprising a serial/parallel converter 30, shift registers of 2 bits 31, 32, 33, modulo-2 adders 34, 35, 36, 37, 42, 43 and a parallel/parallel converter 44.
A data sequence inputted at an input terminal 1 is distributed into three sequences of data by the serial/parallel converter 30 and respectively inputted at shift registers 31, 32, and 33. The outputs of the modulo-2 adders 34, 35, 42, 36, 37 and 43 are respectively expressed in equations below; ##EQU1## The parallel/parallel converter 44 converts these codes in 6 sequences into the codes of 2 sequences, and outputs respectively I and Q channel codes to the output terminals 40, 41 in a manner expressed below; EQU K.sub.I =(K.sub.1, K.sub.3, K.sub.5) EQU K.sub.Q =(K.sub.2, K.sub.4, K.sub.6)
FIG. 12 is a block diagram to show still another convolutional encoder which has the coding rate of K.sub.0 /n.sub.1 =7/14=1/2, and the constraint length of k=7.
An input terminal 1 is connected to a shift register 318 of 7 bits. The first, third, fourth, sixth and seventh bits counting from the side of the input terminal 1 are connected to a modulo-2 adder 330. Similarly, the first, second, third, fourth and seventh bits are connected to a modulo-2 adder 331. The modulo-2 adder 330 is connected to an output terminal 40 to output one channel codes. The modulo-2 adder 331 is connected to an output terminal 41 to output Q channel codes.
In other words, I an Q channel codes are outputted at the output terminals 40, 41 in the manner expressed below; EQU I.sub.t =D.sub.t +D.sub.t+1 +D.sub.t+3 +D.sub.t+4 +D.sub.t +6 EQU Q.sub.t =D.sub.t +D.sub.t +3 +D.sub.t +4+D.sub.t +5 +D.sub.t +6
In the error correcting code method with convolutional coding and maximum likelihood decoding, the larger the redundancy of the code sequence, the greater becomes the correcting capacity similarly with other error correcting methods. But redundancy should preferably be limited in order to increase transmission efficiency. There has been proposed a punctured coding/Viterbi decoding method as a method which is capable of minimizing redundancy or maximizing transmission efficiency and which still is capable of realizing a greater error correcting capacity. (The method is referred to simply as a punctured method hereinafter.)
FIG. 13 is a block diagram to show an error correcting coder/decoder of the punctured method. The transmission side of this decoder comprises an input terminal 1, a convolutional encoder 10, a symbol stealing circuit 11 and a symbol stealing map memory 12, and is connected to the receiver side via a transmission channel 5. The convolutional encoder 10 is a prior art decoder as described above.
Data to be transmitted is inputted at an input terminal 1. The convolutional encoder 10 conducts convolutional encoding of the coding rate R and outputs the convolutional codes. The symbol stealing circuit 11 processes these convolutional codes for conversion into a speed corresponding to the stealing of code symbols and the stealing patterns thereof. The stealing patterns to be used by the symbol stealing circuit 11 are stored by the symbol stealing map memory 12 in advance. The speed conversion process is executed by using, for instance, intermittent clocks. The symbol stealing circuit 11 outputs transmission codes having a coding rate R which is larger than the coding rate R to the transmission path 5.
The receiver side includes a dummy symbol insertion circuit 13, an insertion map memory 14, a maximum likelihood decoder 15 and an output terminal 9.
The dummy symbol insertion circuit 13 inserts dummy symbols into a received transmission code in accordance with the dummy symbol insertion pattern from the insertion map memory 14 to return the mode and the code speed to those of the convolutional codes. The maximum likelihood decoder 15 decodes the output from the dummy symbol insertion code.
FIG. 14 is a block diagram to show the essential components of the circuit on the receiver side. A received signal input terminal 130 receives as input the data from the transmission channel 5 while a synchronization signal input terminal 16 receives as input the code synchronization signals.
The dummy symbol insertion circuit 13 includes a speed converter 131 and a dummy symbol insertion memory 132. The converter 131 converts the speed of received data with speed conversion clocks such as the intermittent clocks which are based on the code synchronization signals. The dummy symbol map memory 132 inserts dummy symbols into the received data whose speed have been converted in accordance with the dummy symbol insertion fed pattern fed from the insertion map memory 14. This produces codes of the same mode as convolutional codes which are subsequently inputted at the maximum likelihood decoder 15.
The maximum likelihood decoder 15 includes a branch metric calculator 73, a path metric calculator 75, a path metric memory circuit 76 and a final decision circuit 77. The branch metric calculator 73 calculates the branch metric out of the output from the dummy symbol insertion circuit 13. The inserted dummy symbols are forcibly given the branch metric in accordance with metric calculation inhibit pulse from the insertion map memory 14 in such a manner that the received symbol becomes a value intermediate between [0] and [1]. The path metric calculator 75, the path memory circuit 76 and the final decision circuit 77 decode the branch metric outputted from the branch metric calculator 73 into original data in accordance with the Viterbi algorithm. The decoded data are outputted to the output terminal 9.
The above mentioned prior art devices are known from the following references:
(1) Japanese Patent Application Laid-open Sho 57 - 155857 PA0 (2) JIECE J64- B Vol. 7 (July, 1981), pp. 573 PA0 (3) Proc. 6th International Conference on Digital Satelite Communications, Phoenix, Sept. 1983, XII 24-XII 31 PA0 (4) IEEE Trans. COMMUN Vol. COM-32, NO. 3, March 1984, pp. 315-319 PA0 (5) IEEE Trans. COMMUN Vol. COM-19, No. 5, Oct. 1971, pp. 751-772
The prior art error correction code decoding device of punctured method, however, inconveniently needs a symbol stealing map memory and a symbol stealing circuit in addition to a convolutional encoder. Moreover, the device further needs to conduct timing control with intermittent clocks in order to conduct the speed conversion as well as stealing of symbols. The receiver side thereof needs a dummy symbol insertion circuit and an insertion map memory in addition to a maximum likelihood decoder corresponding to the convolutional encoder. The receiver side further needs a control in timing intermittent clocks which are required for the speed conversion as well as for insertion of dummy symbols. The prior art device therefore becomes large with respect to circuit scale and complicated in control.
The invention aims at providing an error correcting coder/decoder which can realize maximum likelihood decoding at high efficiency as well as with a high gain but without symbol stealing and dummy symbol insertion which were heretofore required in the punctured method.